package org.ruanjj.dynamicplanning.wordsplit;

import java.util.*;

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> hashSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        int n = s.length();
        for(int j=1; j< n+1; j++){
            for(int i = 0; i < j; i++){
                if(dp[i] && hashSet.contains(s.substring(i,j))) {
                    dp[j] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }
}
